Optimized [rand.dist.samp.pconst] and several bug fixes in other distributions git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@104478 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/random b/include/random index c5f9b17..1a680ff 100644 --- a/include/random +++ b/include/random
@@ -3642,7 +3642,8 @@ const uniform_real_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); return __os << __x.a() << __sp << __x.b(); @@ -3736,7 +3737,8 @@ operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); return __os << __x.p(); @@ -3880,7 +3882,8 @@ const binomial_distribution<_IntType>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); return __os << __x.t() << __sp << __x.p(); @@ -3981,7 +3984,8 @@ const exponential_distribution<_RealType>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); return __os << __x.lambda(); } @@ -4116,7 +4120,8 @@ const normal_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_; @@ -4451,7 +4456,8 @@ const poisson_distribution<_IntType>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); return __os << __x.mean(); } @@ -4542,7 +4548,8 @@ const weibull_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.a() << __sp << __x.b(); @@ -4642,7 +4649,8 @@ const extreme_value_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.a() << __sp << __x.b(); @@ -4795,7 +4803,8 @@ const gamma_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.alpha() << __sp << __x.beta(); @@ -4912,7 +4921,8 @@ const negative_binomial_distribution<_IntType>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); return __os << __x.k() << __sp << __x.p(); @@ -4999,7 +5009,8 @@ const geometric_distribution<_IntType>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); return __os << __x.p(); } @@ -5085,7 +5096,8 @@ const chi_squared_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); __os << __x.n(); return __os; } @@ -5186,7 +5198,8 @@ const cauchy_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.a() << __sp << __x.b(); @@ -5289,7 +5302,8 @@ const fisher_f_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); __os << __x.m() << __sp << __x.n(); @@ -5388,7 +5402,8 @@ const student_t_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); __os << __x.n(); return __os; } @@ -5586,7 +5601,8 @@ const discrete_distribution<_IT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); size_t __n = __x.__p_.__p_.size(); @@ -5627,8 +5643,10 @@ class param_type { - vector<double> __p_; + typedef typename common_type<double, result_type>::type __area_type; vector<result_type> __b_; + vector<double> __densities_; + vector<__area_type> __areas_; public: typedef piecewise_constant_distribution distribution_type; @@ -5643,10 +5661,10 @@ _UnaryOperation __fw); vector<result_type> intervals() const {return __b_;} - vector<double> densities() const; + vector<double> densities() const {return __densities_;} friend bool operator==(const param_type& __x, const param_type& __y) - {return __x.__p_ == __y.__p_ && __x.__b_ == __y.__b_;} + {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;} friend bool operator!=(const param_type& __x, const param_type& __y) {return !(__x == __y);} @@ -5734,29 +5752,27 @@ void piecewise_constant_distribution<_RealType>::param_type::__init() { - if (!__p_.empty()) - { - if (__p_.size() > 1) - { - double __s = _STD::accumulate(__p_.begin(), __p_.end(), 0.0); - for (_STD::vector<double>::iterator __i = __p_.begin(), __e = __p_.end(); - __i < __e; ++__i) - *__i /= __s; - vector<double> __t(__p_.size() - 1); - _STD::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin()); - swap(__p_, __t); - } - else - { - __p_.clear(); - __p_.shrink_to_fit(); - } - } + // __densities_ contains non-normalized areas + __area_type __total_area = _STD::accumulate(__densities_.begin(), + __densities_.end(), + __area_type()); + for (size_t __i = 0; __i < __densities_.size(); ++__i) + __densities_[__i] /= __total_area; + // __densities_ contains normalized areas + __areas_.assign(__densities_.size(), __area_type()); + _STD::partial_sum(__densities_.begin(), __densities_.end() - 1, + __areas_.begin() + 1); + // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1] + __densities_.back() = 1 - __areas_.back(); // correct round off error + for (size_t __i = 0; __i < __densities_.size(); ++__i) + __densities_[__i] /= (__b_[__i+1] - __b_[__i]); + // __densities_ now contains __densities_ } template<class _RealType> piecewise_constant_distribution<_RealType>::param_type::param_type() - : __b_(2) + : __b_(2), + __densities_(1, 1.0) { __b_[1] = 1; } @@ -5772,12 +5788,13 @@ __b_.resize(2); __b_[0] = 0; __b_[1] = 1; + __densities_.assign(1, 1.0); } else { - __p_.reserve(__b_.size() - 1); + __densities_.reserve(__b_.size() - 1); for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__fW) - __p_.push_back(*__fW); + __densities_.push_back(*__fW); __init(); } } @@ -5793,12 +5810,13 @@ __b_.resize(2); __b_[0] = 0; __b_[1] = 1; + __densities_.assign(1, 1.0); } else { - __p_.reserve(__b_.size() - 1); + __densities_.reserve(__b_.size() - 1); for (size_t __i = 0; __i < __b_.size() - 1; ++__i) - __p_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5)); + __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5)); __init(); } } @@ -5811,56 +5829,27 @@ { size_t __n = __b_.size() - 1; result_type __d = (__xmax - __xmin) / __n; - __p_.reserve(__n); + __densities_.reserve(__n); for (size_t __i = 0; __i < __n; ++__i) { __b_[__i] = __xmin + __i * __d; - __p_.push_back(__fw(__b_[__i] + __d*.5)); + __densities_.push_back(__fw(__b_[__i] + __d*.5)); } __b_[__n] = __xmax; __init(); } template<class _RealType> -vector<double> -piecewise_constant_distribution<_RealType>::param_type::densities() const -{ - const size_t __n = __b_.size() - 1; - vector<double> __d(__n); - if (__n == 1) - __d[0] = 1/(__b_[1] - __b_[0]); - else - { - __d[0] = __p_[0] / (__b_[1] - __b_[0]); - for (size_t __i = 1; __i < __n - 1; ++__i) - __d[__i] = (__p_[__i] - __p_[__i-1]) / (__b_[__i+1] - __b_[__i]); - __d[__n-1] = (1 - __p_[__n-2]) / (__b_[__n] - __b_[__n-1]); - } - return __d; -}; - - -template<class _RealType> template<class _URNG> _RealType piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) { typedef uniform_real_distribution<result_type> _Gen; - if (__p.__b_.size() == 2) - return _Gen(__p.__b_[0], __p.__b_[1])(__g); result_type __u = _Gen()(__g); - const vector<double>& __dd = __p.__p_; - size_t __k = static_cast<size_t>(_STD::upper_bound(__dd.begin(), - __dd.end(), static_cast<double>(__u)) - __dd.begin()); - if (__k == 0) - return static_cast<result_type>(__u * (__p.__b_[1] - __p.__b_[0]) / - __dd[0] + __p.__b_[0]); - __u -= __dd[__k-1]; - if (__k == __dd.size()) - return static_cast<result_type>(__u * (__p.__b_[__k+1] - __p.__b_[__k]) / - (1 - __dd[__k-1]) + __p.__b_[__k]); - return static_cast<result_type>(__u * (__p.__b_[__k+1] - __p.__b_[__k]) / - (__dd[__k] - __dd[__k-1]) + __p.__b_[__k]); + ptrdiff_t __k = _STD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(), + static_cast<double>(__u)) - __p.__areas_.begin() - 1; + return static_cast<result_type>((__u - __p.__areas_[__k]) / __p.__densities_[__k] + + __p.__b_[__k]); } template <class _CharT, class _Traits, class _RT> @@ -5869,17 +5858,22 @@ const piecewise_constant_distribution<_RT>& __x) { __save_flags<_CharT, _Traits> _(__os); - __os.flags(ios_base::dec | ios_base::left); + __os.flags(ios_base::dec | ios_base::left | ios_base::fixed | + ios_base::scientific); _CharT __sp = __os.widen(' '); __os.fill(__sp); - size_t __n = __x.__p_.__p_.size(); + size_t __n = __x.__p_.__b_.size(); __os << __n; for (size_t __i = 0; __i < __n; ++__i) - __os << __sp << __x.__p_.__p_[__i]; - __n = __x.__p_.__b_.size(); + __os << __sp << __x.__p_.__b_[__i]; + __n = __x.__p_.__densities_.size(); __os << __sp << __n; for (size_t __i = 0; __i < __n; ++__i) - __os << __sp << __x.__p_.__b_[__i]; + __os << __sp << __x.__p_.__densities_[__i]; + __n = __x.__p_.__areas_.size(); + __os << __sp << __n; + for (size_t __i = 0; __i < __n; ++__i) + __os << __sp << __x.__p_.__areas_[__i]; return __os; } @@ -5891,21 +5885,27 @@ typedef piecewise_constant_distribution<_RT> _Eng; typedef typename _Eng::result_type result_type; typedef typename _Eng::param_type param_type; + typedef typename param_type::__area_type __area_type; __save_flags<_CharT, _Traits> _(__is); __is.flags(ios_base::dec | ios_base::skipws); size_t __n; __is >> __n; - vector<double> __p(__n); - for (size_t __i = 0; __i < __n; ++__i) - __is >> __p[__i]; - __is >> __n; vector<result_type> __b(__n); for (size_t __i = 0; __i < __n; ++__i) __is >> __b[__i]; + __is >> __n; + vector<double> __densities(__n); + for (size_t __i = 0; __i < __n; ++__i) + __is >> __densities[__i]; + __is >> __n; + vector<__area_type> __areas(__n); + for (size_t __i = 0; __i < __n; ++__i) + __is >> __areas[__i]; if (!__is.fail()) { - swap(__x.__p_.__p_, __p); swap(__x.__p_.__b_, __b); + swap(__x.__p_.__densities_, __densities); + swap(__x.__p_.__areas_, __areas); } return __is; } 